package com.major.dawn.leetCode.sort;

// 排序算法，一定要熟悉，这里有很多熟悉的编程的思路和经典写法
//倒序
public class SortArray {

    //    1、选择排序
    public int[] selectSort(int[] nums) {
        int length = nums.length;

        if (length < 2) {
            return nums;
        }

        for (int i = 0; i < length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < length; j++) {
                if (nums[j] < nums[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                swap(i, minIndex, nums);
            }
        }

        return nums;
    }

    private void swap(int i, int minIndex, int[] nums) {
        int tem = nums[i];
        nums[i] = nums[minIndex];
        nums[minIndex] = tem;
    }

    //    2、插入排序
    public int[] insertSort(int[] nums) {
        int length = nums.length;

        if (length < 2) {
            return nums;
        }
        for (int i = 1; i < length; i++) {
            int insertIndex = i;

            while (insertIndex > 0 && nums[i] < nums[insertIndex - 1]) {
                insertIndex--;
            }
            if (insertIndex != i) {
                insert(i, insertIndex, nums);
            }
        }
        return nums;
    }

    private void insert(int i, int insertIndex, int[] nums) {
        int tem = nums[i];
        for (int j = i; j > insertIndex; j--) {
            nums[j] = nums[j - 1];
        }
        nums[insertIndex] = tem;
    }

    //    3、冒泡排序  不知道为什么运行的效率反而变慢了，不能通过测试
    public int[] bubblingSort(int[] nums) {
        int length = nums.length;

        if (length < 2) {
            return nums;
        }

        for (int i = length; i > 0; i--) {
            boolean flag = true;
            for (int j = 1; j < i; j++) {
                if (nums[j] < nums[j - 1]) {
//                    相邻处交换位置
                    swap(j, j - 1, nums);
                    flag = false;
                }
            }

            if (flag) {
                break;
            }
        }

        return nums;
    }

    //    4、并归排序  分而治之的思想，尝试非递归的实现
    public int[] mergeSort(int[] nums) {
        int length = nums.length;

        if (length < 2) {
            return nums;
        }

        int[] forkArray = forkArray(nums);


        return forkArray;
    }

    private int[] forkArray(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return nums;
        }

        if (length == 2) {
            if (nums[0] > nums[1]) {
                int tem = nums[0];
                nums[0] = nums[1];
                nums[1] = tem;
            }
            return nums;
        }
        if (length > 2) {
            int middle = length / 2;

            int[] left = new int[middle];
            System.arraycopy(nums, 0, left, 0, middle);
            int[] forkLeft = forkArray(left);

            int[] right = new int[length-middle];
            System.arraycopy(nums, middle, right, 0, length-middle);
            int[] forkRight = forkArray(right);

            int[] join = join(forkLeft, forkRight, length);
            return join;
        }
        return null;
    }

//    两个有序数组的排序
    private int[] join(int[] left, int[] right,int length) {
        int leftIndex = 0;
        int rightIndex = 0;
        int joinIndex = 0;
        int[] join = new int[length];
        while (leftIndex < left.length && rightIndex < right.length) {
            int cur;
            if (left[leftIndex] < right[rightIndex]) {
                cur = left[leftIndex];
                leftIndex++;
            } else {
                cur = right[rightIndex];
                rightIndex++;
            }
            join[joinIndex] = cur;
            joinIndex++;
        }
        if (leftIndex < left.length) {
            for (int i = leftIndex; i < left.length; i++) {
                join[joinIndex] = left[i];
                joinIndex++;
            }
        }

        if (rightIndex < right.length) {
            for (int i = rightIndex; i < right.length; i++) {
                join[joinIndex] = right[i];
                joinIndex++;
            }
        }
        return join;
    }

    //    4、并归排序  分而治之的思想，非递归的实现
    public int[] mergeSort2(int[] nums) {

        return nums;
    }

//    5、快速排


//    6、堆排序
//    7、桶排序
//    8、基数排序


    public static void main(String[] args) {
        SortArray sortArray = new SortArray();
        int[] nums = new int[]{5, 2, 3, 1};
//        sortArray.selectSort(nums);
//        sortArray.insertSort(nums);
//        sortArray.bubblingSort(nums);
        int[] ints = sortArray.mergeSort(nums);
        for (Integer num : ints) {
            System.out.println(num);
        }
    }
}
